package Leetcode.树;
import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName 叶子相似的树
 * @since: 2023/8/18 16:57
 * @auth: kirito
 * @description:
 * https://leetcode.cn/problems/leaf-similar-trees/?envType=study-plan-v2&envId=leetcode-75
 * 意思就是要求两棵树的叶子节点 从左往右的排序数组要相同
 * 1.从左往右找出来，逐一遍历
 * 2.边找边判断
 **/
public class 叶子相似的树 {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> seq1 = new ArrayList<Integer>();
        if (root1 != null) {
            dfs(root1, seq1);
        }

        List<Integer> seq2 = new ArrayList<Integer>();
        if (root2 != null) {
            dfs(root2, seq2);
        }

        return seq1.equals(seq2);
    }

    public void dfs(TreeNode node, List<Integer> seq) {
       if(node.left == null&&node.right == null){
           seq.add(node.val);
       }else{
           if (node.right != null) {
               dfs(node.right, seq);
           }
           if (node.left != null) {
               dfs(node.left, seq);
           }
       }

    }




}
